# -*- coding: utf-8 -*-

"""
    Time    : 2020/12/21 下午5:31
    Author  : Thinkgamer
    File    : 088-合并两个有序数组.py
    Software: PyCharm
    Desc    : https://leetcode-cn.com/problems/merge-sorted-array/
"""

"""
给你两个有序整数数组nums1 和 nums2，请你将 nums2 合并到nums1中，使 nums1 成为一个有序数组。
说明：
	初始化nums1 和 nums2 的元素数量分别为m 和 n 。
	你可以假设nums1有足够的空间（空间大小大于或等于m + n）来保存 nums2 中的元素。

示例：
输入：
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出：[1,2,2,3,5,6]

提示：
-10^9 <= nums1[i], nums2[i] <= 10^9
nums1.length == m + n
nums2.length == n
"""

"""
	v1: 创建一个临时的数组 nums, 用来存放 nums1 的值 ，然后合并 nums和 nums2 到 nums1
		好像默认是按照升序排列（感觉有争议）
"""


# 12 ms 97.59 % | 13mb 23.10%
def merge_v1(nums1, m, nums2, n):
	nums = nums1[:m]
	i = 0
	j = 0
	ij = 0
	while i < m and j < n:
		if nums[i] < nums2[j]:
			nums1[ij] = nums[i]
			i += 1
		else:
			nums1[ij] = nums2[j]
			j += 1
		ij += 1
	if i < m or j < n:
		while i < m:
			nums1[ij] = nums[i]
			i += 1
			ij += 1
		while j < n:
			nums1[ij] = nums2[j]
			j += 1
			ij += 1
	return nums1


nums1 = [1, 2, 3, 0, 0, 0]
# nums1 = [6, 5, 2, 0, 0, 0]
# nums1 = [1, 0]
m = 3
nums2 = [2, 5, 6]
# nums2 = [3, 2, 1]
# nums2 = [2]
n = 3
result = merge_v1(nums1, m, nums2, n)
print(result)
